package com.linyaonan.leetcode.medium._98;


/**
 * @author: Lin
 * @date: 2020/5/5
 */
public class IsValidBST {

    public long MIN = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        try {
            bfs(root);
        } catch (RuntimeException e) {
            return false;
        }
        return true;
    }

    /**
     * 一棵树左中右的遍历顺序，得到的数值只要不是严格递增的就直接返回不是二叉搜索树
     * @param node
     * @throws RuntimeException
     */
    private void bfs(TreeNode node) throws RuntimeException {
        if (node != null) {
            if (node.left != null) {
                bfs(node.left);
            }
            if (node.val <= MIN) {
                throw new RuntimeException("got it");
            }
            MIN = node.val;
            if (node.right != null) {
                bfs(node.right);
            }
        }
    }

    // 需要注意题目给出的范围在long的范围，使用int有用例异常
    long pre = Long.MIN_VALUE;
    boolean hasError = false;
    public boolean isValidBST2(TreeNode root) {
        bfs2(root);
        return !hasError;
    }

    private void bfs2(TreeNode node) {
        if (node != null) {
            bfs2(node.left);
            if (node.val <= pre) {
                hasError = true;
            }
            pre = node.val;
            bfs2(node.right);
        }
    }
}
